/*
题目：每种字符至少取 k 个
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/description/
 */
public class TakeCharacters {
    int k;
    public int takeCharacters(String s, int k) {
        this.k = k;
        int n = s.length();
        int[] count = new int[3]; // 分别给 a, b, c 计数
        // 考虑前缀和后缀即可
        // 先计算后缀
        int i = 0, j = n;
        while (!isSatisfied(count)) { // 直到找到满足为止
            if (j == 0) { // 由于「先减性」，0 已经计算过了，至此结束
                return -1;
            }
            j --;
            count[s.charAt(j) - 'a'] ++;
        }
        int src = n - j; // 初步判断 - 最终个数
        // 再考虑前缀
        while (i < n) {
            char ch = s.charAt(i ++);
            count[ch - 'a'] ++;
            // 进入这循环肯定是三个都满足的。
            while (j < n && count[s.charAt(j) - 'a'] > k) { // 后缀可以移动
                count[s.charAt(j ++) - 'a'] --;
            }
            src = Math.min(src, i + n - j); // i 在上面提前加了，无需再加一
            if (j >= n) { // 如果 j 已经走完了
                return src; // 就没有优化空间了
            }
        }
        return src;
    }

    public boolean isSatisfied(int[] count) {// 验证是否满足 k
        return count[0] >= k && count[1] >= k && count[2] >= k;
    }
}
